/*
 * @Author: wwssaabb
 * @Date: 2021-11-29 10:05:57
 * @LastEditTime: 2021-11-29 17:31:00
 * @FilePath: \handwritten-code\algorithm\二分查找.js
 */

/* 
给定一个 n 个元素有序的（ 升序） 整型数组 nums 和一个目标值 target， 写一个函数搜索 nums 中的 target， 如果目标值存在返回下标， 否则返回 - 1。

示例 1:

  输入: nums = [-1, 0, 3, 5, 9, 12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

  输入: nums = [-1, 0, 3, 5, 9, 12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 - 1

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/binary-search
*/

//二分法
var search = function (nums, target) {
  let left = 0,
    right = nums.length - 1
  while (left <= right) {
    let mid = Math.floor((right + left) >> 1) //位运算，右移一位想当于除以2
    let num = nums[mid]
    if (num === target) {
      return mid
    } else if (num > target) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return -1
}


console.time(1)
console.log(12345678910 / 2) //符号运算
console.timeEnd(1) //5.47ms
console.time(2)
console.log(12345678910 / 2) //符号运算
console.timeEnd(2) //0.253ms